package com.mlh.graph;

import java.util.HashSet;
import java.util.Stack;

public class DFS {
    public static void DepthFirstSearch(Node node){
        if(node==null){
            return;
        }
        //利用栈
        //将第一个节点入栈
        //访问栈的第一个元素 打印
        // 循环去寻找其未被访问的第一个节点
        //如果有未被访问的 原节点再次压入栈中 然后访问新节点且入栈  break退出
        Stack<Node> stack=new Stack<>();
        HashSet<Node> set=new HashSet<>();
        //放入第一个节点
        stack.push(node);
        set.add(node);
        Node temp=null;
        while(!stack.isEmpty()){
           temp=stack.pop();
           //循环去寻找其未被访问的第一个节点
            for(Node next:temp.nexts){
                if(!set.contains(next)){
                    //如果该元素有未被访问的  还需要将该节点在压入栈中
                    stack.push(temp);
                    stack.push(next);
                    set.add(next);
                    System.out.println(next.value);
                    break;
                }
            }
        }

    }
}
